package lib;

import java.util.Arrays;

import lib.ClosestPair.Pair;

/**
 * 
 * @author  Igor Covganet
 * @Created Aug 6, 2010
 * 
 * The class is tested and works well.
 * 200 000 points are processed in less than 1 second.
 */
public class ClosestPair2 {
	public int ind1 = 0, ind2 = 1;
	public long bestDist;
	
	boolean sortByX = true;
	Pair[] ps, tmpPs;
	public void findClosestPair(int[] xs, int[] ys) {
		bestDist = Long.MAX_VALUE;
		sortByX = true;
		
		tmpPs = new Pair[xs.length];
		ps = new Pair[xs.length];
		for(int i = 0; i < ps.length; i++) {
			ps[i] = new Pair(xs[i], ys[i], i);
		}
		
		Arrays.sort(ps);
		getMinDist(0, xs.length - 1);
	}
	
	void getMinDist(int from, int to) {
		bestDist = Long.MAX_VALUE;
		double dist = Integer.MAX_VALUE;
		
		for(int i = from; i < to; i++) {
			for(int j = i + 1; j <= to; j++) {
				if(ps[j].x - ps[i].x >= dist) {
					break;
				}
				long d = ps[i].distTo(ps[j]);
				if(bestDist > d) {
					bestDist = d;
					dist = Math.sqrt(d);
					ind1 = ps[i].ind;
					ind2 = ps[j].ind;
					if(bestDist == 0) {
						return;
					}
				}
			}
		}
	}
	
	class Pair implements Comparable<Pair> {
		int x, y, ind;
		
		public Pair(int x, int y, int ind) {
			this.x = x;
			this.y = y;
			this.ind = ind;
		}
		@Override
		public int compareTo(Pair o) {
			if(x != o.x) {
				return x - o.x;
			}
			
			return y - o.y;
		}
		
		public long distTo(Pair p2) {
			return (long)(p2.x - x) * (p2.x - x) + (long)(p2.y - y) * (p2.y - y);
		}
	}
}
